/*
集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。

给定一个数组 nums 代表了集合 S 发生错误后的结果。

请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/set-mismatch
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
#include <vector>
using namespace std;
// class Solution
// {
// public:
//     vector<int> findErrorNums(vector<int> &nums)
//     {
//         vector<int> ans;
//         vector<int> counter(nums.size(), 0);
//         for (int i = 0; i < nums.size(); i++)
//         {
//             counter[nums[i] - 1]++;
//         }
//         int repeat, nonEx;
//         for (int i = 0; i < nums.size(); i++)
//         {
//             if (counter[i] == 2)
//             {
//                 repeat = i + 1;
//             }
//             else if (counter[i] == 0)
//             {
//                 nonEx = i + 1;
//             }
//         }
//         ans.push_back(repeat);
//         ans.push_back(nonEx);
//         return ans;
//     }
// };
class Solution {
public:
// 官方题解，方法三：位运算。因为只有目标数字出现的次数为偶数，令所有数字多出现一次。
// 所有数字异或，得到的结果为两个目标数字异或。
// 找到异或数值的最低位，将所有数字分为两组，两个目标数字必然分开。从而可以找到两个数字。
// 遍历数组最后找到两个目标数字的顺序，确定答案。
    vector<int> findErrorNums(vector<int>& nums) {
        int n = nums.size();
        int xorSum = 0;
        for (int num : nums) {
            xorSum ^= num;
        }
        for (int i = 1; i <= n; i++) {
            xorSum ^= i;
        }
        int lowbit = xorSum & (-xorSum);
        int num1 = 0, num2 = 0;
        for (int &num : nums) {
            if ((num & lowbit) == 0) {
                num1 ^= num;
            } else {
                num2 ^= num;
            }
        }
        for (int i = 1; i <= n; i++) {
            if ((i & lowbit) == 0) {
                num1 ^= i;
            } else {
                num2 ^= i;
            }
        }
        for (int num : nums) {
            if (num == num1) {
                return vector<int>{num1, num2};
            }
        }
        return vector<int>{num2, num1};
    }
};
